class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1 or n == 2: return n
        nums = [0] * (n+1)
        nums[0], nums[1], nums[2] = 0, 1, 2
        for i in range(3, len(nums)):
            nums[i] = nums[i-1] + nums[i-2]
        return nums[n]
if __name__ == '__main__':
    s = Solution()
    n = 0
    n = 1
    n = 2
    n = 3
    n = 4
    result = s.climbStairs(n)
    print(result)